package com.zjsru.plan2023.oneday.oneDay202302;

import java.util.Arrays;

/**
 * @Author: CookLee
 * @Date: 2023/2/4
 * 你能构造出连续值的最大数目： 构造 出多少个 连续 整数。
 *
 * 输入：coins = [1,3]
 * 输出：2
 * 解释：你可以得到以下这些值：
 * - 0：什么都不取 []
 * - 1：取 [1]
 * 从 0 开始，你可以构造出 2 个连续整数。
 *
 * 输入：coins = [1,1,1,4]
 * 输出：8
 * 解释：你可以得到以下这些值：
 * - 0：什么都不取 []
 * - 1：取 [1]
 * - 2：取 [1,1]
 * - 3：取 [1,1,1]
 * - 4：取 [4]
 * - 5：取 [4,1]
 * - 6：取 [4,1,1]
 * - 7：取 [4,1,1,1]
 * 从 0 开始，你可以构造出 8 个连续整数。
 */
public class GetMaximumConsecutive {
    
    /**
     * 贪心
     *
     * @param coins 硬币
     * @return int
     */
    public int getMaximumConsecutive(int[] coins) {
        //第一个数字的值是0
        int ans = 1;
        Arrays.sort(coins);
        //数字排序后，如果ans的值小于某个硬币值 则表示相加后缺少一段数字
        //按测试用例： 最后以为ans = 4，最后一个硬币 = 4时  （0，1，2，3） + 4 能构造出 4，5，6，7
        //如果ans = 4，最后一个硬币 = 5时  （0，1，2，3） + 5 能构造出 5，6，7，8 缺少4
        for (int num : coins) {
            if (num > ans) {
                //无法构造出 ans
                break;
            }
            //可以构造出区间 [0,num+ans] 中的所有整数
            ans += num;
        }
        return ans;
    }
    
    public static void main(String[] args) {
        GetMaximumConsecutive getMaximumConsecutive = new GetMaximumConsecutive();
        int[] coins = new int[] {1, 1, 1, 4};
        System.out.println(getMaximumConsecutive.getMaximumConsecutive(coins));
    }
}
